//#include <iostream>
//#include <stack>
//using namespace std;
//
//bool isValid(string s) {
//    stack<char> ok;
//    int n = s.size();
//    for (int i = 0; i < n; i++){
//        if (s[i] == '(' || s[i] == '{' || s[i] == '[')
//            ok.push(s[i]);
//        else {
//            if (!ok.size())
//                return false;
//            char a = ok.top();
//            if (a == '(' && s[i] != ')')
//                return false;
//            if (a == '[' && s[i] != ']')
//                return false;
//            if (a == '{' && s[i] != '}')
//                return false;
//            ok.pop();
//        }
//        
//    }
//    if(ok.size())
//    return true;
//}
//int main() {
//	ios::sync_with_stdio(0);
//    string s;
//    cin >> s;
//    bool flag = isValid(s);
//    cout << flag;
//    return 0;
//}

//class Solution {
//public:
//    bool isValid(string s) {
//        stack<char> ok;
//        int n = s.size();
//        for (int i = 0; i < n; i++) {
//            if (s[i] == '(' || s[i] == '{' || s[i] == '[')
//                ok.push(s[i]);
//            else {
//                if (!ok.size())
//                    return false;
//                char a = ok.top();
//                if (a == '(' && s[i] != ')')
//                    return false;
//                if (a == '[' && s[i] != ']')
//                    return false;
//                if (a == '{' && s[i] != '}')
//                    return false;
//                ok.pop();
//            }
//
//        }
//        if (ok.size())
//            return false;
//        return true;
//    }
//};